#pragma once
#include <list>
using namespace std;
/// <summary>
/// Store items in a binary tree for faster sorting.
/// </summary>
/// <typeparam name="T">Type of item.</typeparam>
template <typename T> class SortedList
{
public:
	T* Item;
	SortedList<T>* GreaterThan;
	SortedList<T>* LessThan;
	int branchCount;
	/// <summary>
	/// Constructor
	/// </summary>
	/// <param name="item">Item</param>
	SortedList(T* item)
	{
		Item = item;
		GreaterThan = NULL;
		LessThan = NULL;
	}

	/// <summary>
	/// Clear the list. Deletes the Item and deletes the child items.
	/// </summary>
	void Clear()
	{
		list<SortedList<T>*> items;
		SortedList<T>* nextItem;

		// It's easy to code a recurive delete. But recursive delete can sometimes crash the stack if the tree is big.
		if (Item != NULL)
		{
			delete Item;
			Item = NULL;
		}
		if (LessThan != NULL)
		{
			items.push_back(LessThan);
			LessThan = NULL;
		}
		if (GreaterThan != NULL)
		{
			items.push_back(GreaterThan);
			GreaterThan = NULL;
		}
		while (!items.empty())
		{
			nextItem = items.front();
			items.pop_front();
			if (nextItem->LessThan != NULL)
			{
				items.push_back(nextItem->LessThan);
				nextItem->LessThan = NULL;
			}
			if (nextItem->GreaterThan != NULL)
			{
				items.push_back(nextItem->GreaterThan);
				nextItem->GreaterThan = NULL;
			}
			
			delete nextItem;
		}
	}
	/// <summary>
	/// Destructor.
	/// </summary>
	~SortedList()
	{
		Clear();
	}
	/// <summary>
	/// Searches for an item.
	/// </summary>
	/// <param name="item">Item to search for</param>
	/// <param name="compareFunction">Compare function used for searching</param>
	/// <param name="addIfNotAlreadThere">If true, then add the item if it's not found.</param>
	/// <returns>Returns true if the item was found</returns>
	bool Find(T* item,int (compareFunction)(const T *item1,const T *item2),bool addIfNotAlreadThere)
	{
		SortedList<T>* loop = this;
		int compare;
		bool found = false;
		while (loop != NULL)
		{
			compare = compareFunction(item, loop->Item);
			if (compare == 0)
			{
				found = true;
				break;
			}
			if (addIfNotAlreadThere)
			{
				if (compare < 0)
				{
					if (loop->LessThan != NULL)
					{
						loop = loop->LessThan;
					}
					else
					{
						loop->LessThan = new SortedList<T>(item);
						break;
					}
				}
				else
				{
					if (loop->GreaterThan != NULL)
					{
						loop = loop->GreaterThan;
					}
					else
					{
						loop->GreaterThan = new SortedList<T>(item);
						break;
					}
				}
			}
			else
			{
				loop = compare < 0 ? loop->LessThan : loop->GreaterThan;
			}
		}
		return found;
	}
};
